package Queue_and_Stack;

/*
图像渲染
有一幅以m x n的二维整数数组表示的图画image，其中image[i][j]表示该图画的像素值大小。你也被给予三个整数 sr , sc 和 color 。
你应该从像素image[sr][sc]开始对图像进行上色填充 。
为了完成 上色工作：
从初始像素开始，将其颜色改为 color。
对初始坐标的 上下左右四个方向上 相邻且与初始像素的原始颜色同色的像素点执行相同操作。
通过检查与初始像素的原始颜色相同的相邻像素并修改其颜色来继续 重复 此过程。
当 没有 其它原始颜色的相邻像素时 停止 操作。
最后返回经过上色渲染修改 后的图像。

示例 1:
输入：image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, color = 2
输出：[[2,2,2],[2,2,0],[2,0,1]]
解释：在图像的正中间，坐标 (sr,sc)=(1,1)（即红色像素）,在路径上所有符合条件的像素点的颜色都被更改成相同的新颜色（即蓝色像素）。
注意，右下角的像素 没有 更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。
示例 2:
输入：image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
输出：[[0,0,0],[0,0,0]]
解释：初始像素已经用 0 着色，这与目标颜色相同。因此，不会对图像进行任何更改。
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/queue-stack/g02cj/
 */

import java.util.Deque;
import java.util.LinkedList;

public class _54图像渲染 {
    public static void main(String[] args) {

    }

    //BFS
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int c = image[sr][sc];
        if(c == color){
            return image;
        }
        Deque<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cx = cur[0], cy = cur[1];
            image[cx][cy] = color;
            int left = Math.max(cx - 1, 0);
            int right = Math.min(cx + 1, image.length - 1);
            int top = Math.max(cy - 1, 0);
            int bottom = Math.min(cy + 1, image[0].length - 1);
            if(image[left][cy] == c) {
                queue.offer(new int[]{left, cy});
                image[left][cy] = color;
            }
            if(image[right][cy] == c) {
                queue.offer(new int[]{right, cy});
                image[right][cy] = color;
            }
            if(image[cx][top] == c) {
                queue.offer(new int[]{cx, top});
                image[cx][top] = color;
            }
            if(image[cx][bottom] == c) {
                queue.offer(new int[]{cx, bottom});
                image[cx][bottom] = color;
            }
        }
        return image;
    }

    //DFS
    public int[][] floodFill2(int[][] image, int sr, int sc, int color) {
        int c = image[sr][sc];
        if (c == color) {
            return image;
        }
        changecolor(image, sr, sc, c, color);
        return image;
    }

    public void changecolor(int[][] image, int sr, int sc, int color, int newcolor) {
        if (sr > image.length - 1 || sr < 0) {
            return;
        }
        if (sc > image[0].length - 1 || sc < 0) {
            return;
        }
        if (image[sr][sc] == color) {
            image[sr][sc] = newcolor;
        } else {
            return;
        }
        changecolor(image, sr - 1, sc, color, newcolor);
        changecolor(image, sr + 1, sc, color, newcolor);
        changecolor(image, sr, sc - 1, color, newcolor);
        changecolor(image, sr, sc + 1, color, newcolor);
    }
}
